{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Operations to Make Array Continuous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组连续的最少操作数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;。每一次操作中，你可以将&nbsp;<code>nums</code>&nbsp;中&nbsp;<strong>任意</strong>&nbsp;一个元素替换成 <strong>任意&nbsp;</strong>整数。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>nums</code>&nbsp;满足以下条件，那么它是 <strong>连续的</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums</code>&nbsp;中所有元素都是 <b>互不相同</b>&nbsp;的。</li>\n",
    "\t<li><code>nums</code>&nbsp;中 <strong>最大</strong>&nbsp;元素与&nbsp;<strong>最小</strong>&nbsp;元素的差等于&nbsp;<code>nums.length - 1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说，<code>nums = [4, 2, 5, 3]</code>&nbsp;是 <strong>连续的</strong>&nbsp;，但是&nbsp;<code>nums = [1, 2, 3, 5, 6]</code> <strong>不是连续的</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回使 <code>nums</code>&nbsp;<strong>连续</strong>&nbsp;的 <strong>最少</strong>&nbsp;操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [4,2,5,3]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>nums 已经是连续的了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,3,5,6]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>一个可能的解是将最后一个元素变为 4 。\n",
    "结果数组为 [1,2,3,5,4] ，是连续数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,10,100,1000]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>一个可能的解是：\n",
    "- 将第二个元素变为 2 。\n",
    "- 将第三个元素变为 3 。\n",
    "- 将第四个元素变为 4 。\n",
    "结果数组为 [1,2,3,4] ，是连续数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-operations-to-make-array-continuous](https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-continuous/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-operations-to-make-array-continuous](https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-continuous/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,5,3]', '[1,2,3,5,6]', '[1,10,100,1000]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a=[]\n",
    "        t=0\n",
    "        s=len(nums)\n",
    "        x=s\n",
    "        p=0\n",
    "        flag=False\n",
    "        for i in nums:\n",
    "            if i==1:\n",
    "                flag=True\n",
    "                p+=1\n",
    "        if flag:\n",
    "            return x-p\n",
    "        \n",
    "\n",
    "        while True:\n",
    "            t+=1\n",
    "            for i in range(s-1):\n",
    "                nums[i]=gcd(nums[i],nums[i+1])\n",
    "                if nums[i]==1:\n",
    "                    return t+x-1\n",
    "            nums.pop()\n",
    "            s-=1\n",
    "                \n",
    "            if s==1:\n",
    "                return -1\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if reduce(gcd, nums) > 1:\n",
    "            return -1\n",
    "        if min(nums) == 1:\n",
    "            return sum([1 for i in nums if i > 1]) \n",
    "        n = len(nums)\n",
    "        d = n - 1\n",
    "        for i in range(n - 1):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if tmp == 1:\n",
    "                    d = min(d, j - i)\n",
    "                    break\n",
    "        return d + n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums)>1:\n",
    "            return -1\n",
    "        n=len(nums)\n",
    "        cnt1=sum(x==1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n-cnt1\n",
    "\n",
    "        min_size=n\n",
    "        for i in range(n):\n",
    "            g=0\n",
    "            for j in range(i,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1:\n",
    "                    min_size=min(min_size,j-i)\n",
    "                    break\n",
    "        return min_size+n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "                # 如果所有数的gcd>1，return -1\n",
    "        # 1如果有1，return n-count1\n",
    "        # 2如果没有1，return minsize-1+n-1\n",
    "        from math import gcd\n",
    "        if gcd(*nums)>1:return -1\n",
    "        cnt1=sum(num==1 for num in nums)\n",
    "        n=len(nums)\n",
    "        if cnt1:return n-cnt1\n",
    "        minsize=n\n",
    "        for i in range(n):\n",
    "            g=nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize,j-i+1)\n",
    "                    break \n",
    "        return minsize+n-2\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1 != 0:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        min_len = float('inf')\n",
    "        n = len(nums)\n",
    "        one_cnt = nums.count(1)\n",
    "        if one_cnt:\n",
    "            return n - one_cnt\n",
    "        for i in range(n - 1):\n",
    "            g = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_len = min(min_len, j - i + 1)\n",
    "        return n - 1 + (min_len - 1) if min_len != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        minn=9999999\n",
    "        if 1 in nums:\n",
    "            return len(nums)-nums.count(1)\n",
    "        l=len(nums)\n",
    "        temp2=0\n",
    "        for i in range(l-1):\n",
    "            temp=nums[i]\n",
    "            for j in range(i+1,l):\n",
    "                if math.gcd(temp,nums[j])==1:\n",
    "                    temp=math.gcd(temp,nums[j])\n",
    "                    if j-i<minn:\n",
    "                        minn=j-i\n",
    "                    temp2=-1\n",
    "                else:\n",
    "                    temp=math.gcd(temp,nums[j])\n",
    "            if temp2==0:\n",
    "                return -1\n",
    "        return l+minn-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) >1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n-cnt1\n",
    "        minsize = n\n",
    "        for i in range(n):\n",
    "            g =  0\n",
    "            for j in range(i,n):\n",
    "                g = gcd(g,nums[j])\n",
    "                if g == 1:\n",
    "                    minsize = min(minsize,j-i)\n",
    "                    break\n",
    "        return minsize+n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        # 质因数分解 \r\n",
    "        # 如果 所有数字都有相同质因数那么返回 -1 \r\n",
    "        # 否则返回最快变1操作数 + (len(num1) - 1)\r\n",
    "\r\n",
    "        # 我以为随便选两个数，，，，绷不住了 \r\n",
    "        # \r\n",
    "        n = len(nums)\r\n",
    "        # def divx(x: int) -> List[int]:\r\n",
    "        #     dx = []\r\n",
    "        #     for i in range(2, isqrt(x) + 1):\r\n",
    "        #         if x % i == 0:\r\n",
    "        #             dx.append(i)\r\n",
    "        #             while x % i == 0:\r\n",
    "        #                 x //= i \r\n",
    "        #     if x > 1:\r\n",
    "        #         dx.append(x)\r\n",
    "        #     return dx\r\n",
    "                \r\n",
    "        # res = inf \r\n",
    "        # for x in nums:\r\n",
    "        #     d = divx(x)\r\n",
    "        #     dp = [[inf] * (1 << len(d)) for _ in range(n + 1)]\r\n",
    "        #     for i in range(n + 1):\r\n",
    "        #         dp[i][0] = 0\r\n",
    "        #     for i in range(n):\r\n",
    "        #         m = 0\r\n",
    "        #         for k, y in enumerate(d):\r\n",
    "        #             if nums[i] % y == 0:\r\n",
    "        #                 m |= (1 << k) \r\n",
    "        #         for j in range(1 << (len(d))):\r\n",
    "        #             dp[i + 1][j] = min(dp[i][j], dp[i][j&m] + 1)\r\n",
    "        #     if dp[-1][- 1] == inf:\r\n",
    "        #         return -1 \r\n",
    "        #     res = min(res, dp[-1][-1] + (n - 1)) \r\n",
    "        #     print(dp)\r\n",
    "        # return res if res != inf else -1 \r\n",
    "        cnt = sum(x == 1 for x in nums)\r\n",
    "        if cnt:\r\n",
    "            return n - cnt \r\n",
    "        \r\n",
    "        res = inf\r\n",
    "        for i in range(n):\r\n",
    "            g = nums[i]\r\n",
    "            for j in range(i, n):\r\n",
    "                g = gcd(g, nums[j])\r\n",
    "                if g == 1:\r\n",
    "                    res = min((j - i) + (n - 1), res)\r\n",
    "        return res if res != inf else -1 \r\n",
    "    \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tmp = nums.copy()\n",
    "        ans = n-nums.count(1)\n",
    "        while tmp:\n",
    "            for i in range(len(tmp)-1):\n",
    "                tmp[i] = gcd(tmp[i], tmp[i+1])\n",
    "                if tmp[i] == 1:\n",
    "                    return ans\n",
    "            ans += 1 # length of [i,j] interval (that make 1 happen) + 1\n",
    "            tmp.pop()\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        cnt1 = sum(num == 1 for num in nums)\n",
    "        \n",
    "        if cnt1 > 0:\n",
    "            return n - cnt1\n",
    "        \n",
    "        min_cnt = inf\n",
    "\n",
    "        for i in range(n-1):\n",
    "            gcd_res = nums[i]\n",
    "            for j in range(i+1, n):\n",
    "                gcd_res = gcd(nums[j], gcd_res)\n",
    "                \n",
    "                if gcd_res == 1:\n",
    "                    min_cnt = min(min_cnt, j - i)\n",
    "                    break\n",
    "                    \n",
    "        return n + min_cnt - 1 if min_cnt < inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, A: List[int]) -> int:\n",
    "        return len(A) - A.count(1) if 1 in A else -1 if gcd(*A) != 1 else len(A) + min(j - i for i, j in combinations(range(len(A) + 1), 2) if 1 == gcd(*A[i: j])) - 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def gcd(x,y):\n",
    "            if y%x==0 or x%y==0:\n",
    "                return min(x,y)\n",
    "            return gcd(max(x,y)%min(x,y),min(x,y))\n",
    "        res=nums[0]\n",
    "        for num in nums:\n",
    "            res=gcd(res,num)\n",
    "        if res>1:\n",
    "            return -1\n",
    "        cnt=0\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                cnt+=1\n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        def check(x):\n",
    "            for i in range(n):\n",
    "                res=nums[i]\n",
    "                for j in range(1,x):\n",
    "                    if i+j<n:\n",
    "                        res=gcd(res,nums[i+j])\n",
    "                        if res==1:\n",
    "                            return True\n",
    "            return False\n",
    "                \n",
    "\n",
    "        \n",
    "        left,right=n-1,2*n-1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid-n+1):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        min_len = float('inf')\n",
    "        n = len(nums)\n",
    "        one_cnt = nums.count(1)\n",
    "        if one_cnt:\n",
    "            return n - one_cnt\n",
    "        for i in range(n - 1):\n",
    "            g = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_len = min(min_len, j - i + 1)\n",
    "        return n - 1 + (min_len - 1) if min_len != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        n_one = nums.count(1)\n",
    "        if n_one:\n",
    "            return n - n_one\n",
    "        \n",
    "        min_len = n\n",
    "        for i in range(n):\n",
    "            min_gcd = 0\n",
    "            for k in range(i,n):\n",
    "                min_gcd = gcd(min_gcd, nums[k])\n",
    "                if min_gcd == 1:\n",
    "                    min_len = min(min_len, k - i)\n",
    "                    break\n",
    "            \n",
    "            if min_len == 1:\n",
    "                break\n",
    "\n",
    "        return min_len + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a:int,b:int)->int:\n",
    "            while b != 0:\n",
    "                a,b = b,a%b\n",
    "            return a\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        dis = inf\n",
    "        for i in range(n):\n",
    "            ones += 1 if nums[i] == 1 else 0\n",
    "            a = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                a = gcd(a,nums[j])\n",
    "                if a == 1:\n",
    "                    dis = min(dis,j-i)\n",
    "        if ones:\n",
    "            return n - ones\n",
    "        elif dis == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return n + dis - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a1 = 0\n",
    "        tmp = nums[0]\n",
    "        if nums[0]==1:\n",
    "            a1+=1\n",
    "        for i in nums[1:]:\n",
    "            tmp=gcd(tmp,i)\n",
    "            if i==1:\n",
    "                a1+=1\n",
    "        if tmp!=1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        if a1>0:\n",
    "            return n-a1\n",
    "        res = n\n",
    "        for i in range(n):\n",
    "            t = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                t = gcd(t,nums[j])\n",
    "                if t==1:\n",
    "                    res=min(res,j-i+1)\n",
    "        return n+res-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        t = sum(1 for i in nums if i == 1)\n",
    "        if t:\n",
    "            return n - t\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        a = nums.copy()\n",
    "        for t in range(1, n):\n",
    "            a.pop()\n",
    "            for i, c in enumerate(a):\n",
    "                a[i] = gcd(c, nums[i + t])\n",
    "                if a[i] == 1:\n",
    "                    return n + t - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt_1 = 0\n",
    "        for num in nums:\n",
    "            cnt_1 += (num == 1)\n",
    "        if cnt_1 > 0:\n",
    "            return n - cnt_1\n",
    "        l = 1\n",
    "        f = copy.deepcopy(nums)\n",
    "        while l < n:\n",
    "            for i in range(0, n - l):\n",
    "                f[i] = gcd(f[i], nums[i + l])\n",
    "                if f[i] == 1:\n",
    "                    return n + l - 1\n",
    "            l += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def gcd(x, y):\n",
    "            while y:\n",
    "                tmp = y\n",
    "                y = x % y \n",
    "                x = tmp \n",
    "            return x \n",
    "        cnt = nums.count(1)\n",
    "        def check(start, end):\n",
    "            g = nums[start]\n",
    "            for i in range(start + 1, end + 1):\n",
    "                g = gcd(g, nums[i])\n",
    "            return g == 1 \n",
    "        if cnt > 0:\n",
    "            return n - cnt \n",
    "        l = 0\n",
    "        res = float('inf')\n",
    "        for r in range(n):\n",
    "            while l < r and check(l, r):\n",
    "                res = min(res, r - l + n - 1)\n",
    "                l += 1 \n",
    "        return res if res != float('inf') else - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 如果所有的相邻的两个数都大于 1，且 gcd 都大于 自身，意味着 gcd 不会更小，那么返回 -1\n",
    "        # 否则找到一个连续子数组，对其 gcd 得到第一个 1\n",
    "        # 以题目的 [2,6,3,4] 为例，我们得到了 [2, 6, 3, 1]\n",
    "        # 接下来用 1 和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        # 特殊地，如果数组中已经有 1 了，那么直接和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            cnt += num == 1\n",
    "        if cnt > 0: return len(nums) - cnt\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            g = nums[i]\n",
    "            cnt = 0\n",
    "            for j in range(i+1, len(nums)):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                cnt += 1\n",
    "                if g == 1:# 从 i 到 j 的子数组 gcd 是 1， 那么我们就先对其 gcd，操作数为 cnt，再加上扩展的操作数为 len(nums) - 1\n",
    "                    ans = min(ans, len(nums) - 1 + cnt)\n",
    "                    break # 提前退出\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        a = []  # [GCD，相同 GCD 闭区间的右端点]\n",
    "        for i, x in enumerate(nums):\n",
    "            a.append([x, i])\n",
    "\n",
    "            # 原地去重，因为相同的 GCD 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "\n",
    "            if a[0][0] == 1:\n",
    "                # 这里本来是 i-a[0][1]+1，把 +1 提出来合并到 return 中\n",
    "                min_size = min(min_size, i - a[0][1])\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 原本如果数组里有1，那么最少操作数是 n - cnt\n",
    "        # 如果没有1，那么就最短的gcd为1的子数组构造出一个1\n",
    "        n = len(nums)\n",
    "        g = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            g = math.gcd(g,num)\n",
    "            if num == 1:\n",
    "                cnt+=1\n",
    "        if g!=1:\n",
    "            return -1\n",
    "        \n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        minsize = n+1\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i,n):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize, j-i+1)\n",
    "        return minsize + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 如果相邻的两个数大于 1，且 gcd 都大于 自身，意味着 gcd 不会更小，那么返回 -1\n",
    "        # 否则找到一对，进行 gcd 直到等于 1，我们得到了一个 1\n",
    "        # 以题目的 [2,6,3,4] 为例，我们得到了 [2, 6, 3, 1]\n",
    "        # 接下来用 1 和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        # 特殊地，如果数组中已经有 1 了，那么直接和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            cnt += num == 1\n",
    "        if cnt > 0: return len(nums) - cnt\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            g = nums[i]\n",
    "            cnt = 0\n",
    "            for j in range(i+1, len(nums)):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                cnt += 1\n",
    "                if g == 1:\n",
    "                    ans = min(ans, len(nums) - 1 + cnt)\n",
    "                    break\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=inf\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                ans=1\n",
    "                break\n",
    "            else:\n",
    "                g=nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1: ans=min(ans,j-i+1)\n",
    "        print(ans)\n",
    "        if ans==inf:return -1\n",
    "        elif ans==1: return n-nums.count(1)\n",
    "        elif ans==2: return n\n",
    "        else: return ans-2+n\n",
    "        #n=4, ans=2\n",
    "        #n=3, ans=3\n",
    "        #n=5, ans=3\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        arr=nums\n",
    "        st=[]\n",
    "        min_size=n\n",
    "        for i,a in enumerate(arr):\n",
    "            for j in range(len(st)):\n",
    "                st[j][0]=gcd(st[j][0],a)\n",
    "            nst=[]\n",
    "            for v,j in st:\n",
    "                if len(nst)==0 or v!=nst[-1][0]:\n",
    "                    nst.append([v,j])\n",
    "            nst.append([a,i])\n",
    "            for j in range(len(nst)-1):\n",
    "                v,s,e=nst[j][0],nst[j][1],nst[j+1][1]-1\n",
    "            st=nst\n",
    "            if st[0][0]==1:\n",
    "                min_size=min(min_size,i-(st[1][1]-1)+1)\n",
    "            #print(st)\n",
    "            if len(st)>1 and st[-1][0]==st[-2][0]:\n",
    "                st.pop()\n",
    "        return min_size + n - 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1%num2)\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 1):\n",
    "                ones += 1\n",
    "        if(ones > 0):\n",
    "            return n - ones\n",
    "        min_size = float('inf')\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if(tmp == 1):\n",
    "                    min_size = min(min_size, j-i+1)\n",
    "        if(min_size == float('inf')):\n",
    "            return -1\n",
    "        else:\n",
    "            return n - 1 + min_size - 1\n",
    "                \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a:int,b:int)->int:\n",
    "            while b != 0:\n",
    "                a,b = b,a%b\n",
    "            return a\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        a = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        dis = inf\n",
    "        for i in range(n):\n",
    "            ones += 1 if nums[i] == 1 else 0\n",
    "            a[i][i] = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                a[i][j] = gcd(a[i][j-1],nums[j])\n",
    "                if a[i][j] == 1:\n",
    "                    dis = min(dis,j-i)\n",
    "        if ones:\n",
    "            return n - ones\n",
    "        elif dis == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return n + dis - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if 1 in nums:\n",
    "            return len(nums) - nums.count(1)\n",
    "        n = len(nums)\n",
    "        if reduce(gcd, nums) != 1:\n",
    "            return -1\n",
    "        for l in range(2, 51):\n",
    "            for i in range(n - l + 1):\n",
    "                if reduce(gcd, nums[i: i + l]) == 1:\n",
    "                    return l + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                count += 1\n",
    "        if count > 0:\n",
    "            return len(nums) - count\n",
    "        minlength = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                if gcd(*nums[i:j]) == 1:\n",
    "                    minlength = min(minlength, j - i)\n",
    "        return minlength + len(nums) - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            g = math.gcd(g,num)\n",
    "            if num == 1:\n",
    "                cnt+=1\n",
    "        if g!=1:\n",
    "            return -1\n",
    "        \n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        minsize = n+1\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i,n):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize, j-i+1)\n",
    "        return minsize + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1%num2)\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 1):\n",
    "                ones += 1\n",
    "        if(ones > 0):\n",
    "            return n - ones\n",
    "        min_size = float('inf')\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if(tmp == 1):\n",
    "                    min_size = min(min_size, j-i+1)\n",
    "        if(min_size == float('inf')):\n",
    "            return -1\n",
    "        else:\n",
    "            return n - 1 + min_size - 1\n",
    "                \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                count += 1\n",
    "        if count > 0:\n",
    "            return len(nums) - count\n",
    "        minlength = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                if gcd(*nums[i:j]) == 1:\n",
    "                    minlength = min(minlength, j - i)\n",
    "        return minlength + len(nums) - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(x, y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcd(y % x, x)\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for nu in nums:\n",
    "            if nu == 1:\n",
    "                cnt += 1\n",
    "        if cnt != 0:\n",
    "            return n - cnt\n",
    "        ans = 100\n",
    "        for i in range(n):\n",
    "            res = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                res = gcd(res, nums[j])\n",
    "                if res == 1:\n",
    "                    ans = min(ans, j - i + n - 1)\n",
    "                    break\n",
    "        if ans == 100:\n",
    "            return -1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1 :\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        \n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i + 1)\n",
    "                    break\n",
    "        \n",
    "        return min_size + n - 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n, cnt1 = len(nums), sum(x==1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        \n",
    "        g, min_size = [], n\n",
    "        for i, x in enumerate(nums):\n",
    "            g.append([x, i])\n",
    "\n",
    "            j = 0\n",
    "            for p in g:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if g[j][0] == p[0]:\n",
    "                    g[j][1] = p[1]\n",
    "                else:\n",
    "                    j += 1\n",
    "                    g[j] = p\n",
    "            del g[j+1:]\n",
    "\n",
    "            if g[0][0] == 1:\n",
    "                min_size = min(min_size, i-g[0][1]+1)\n",
    "        return min_size + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def gcd(x,y):\n",
    "            if y%x==0 or x%y==0:\n",
    "                return min(x,y)\n",
    "            return gcd(max(x,y)%min(x,y),min(x,y))\n",
    "        res=nums[0]\n",
    "        for num in nums:\n",
    "            res=gcd(res,num)\n",
    "        if res>1:\n",
    "            return -1\n",
    "        cnt=0\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                cnt+=1\n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        def check(x):\n",
    "            for i in range(n):\n",
    "                res=nums[i]\n",
    "                for j in range(1,x):\n",
    "                    if i+j<n:\n",
    "                        res=gcd(res,nums[i+j])\n",
    "                        if res==1:\n",
    "                            return True\n",
    "            return False\n",
    "                \n",
    "\n",
    "        \n",
    "        left,right=n-1,2*n-1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid-n+1):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "\n",
    "        cnt1 =sum(x == 1 for x in nums)        \n",
    "\n",
    "        if cnt1:\n",
    "            return n -cnt1\n",
    "        min_size = n\n",
    "        g = []\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            g.append([x,i])\n",
    "            ## 相同的 gcd 在一起\n",
    "            j = 0\n",
    "            for p in g :\n",
    "                p[0] = gcd(p[0],x)\n",
    "                if g[j][0]!=p[0]:\n",
    "                    j +=1\n",
    "                    g[j] = p\n",
    "                else:\n",
    "                    g[j][1] = p[1]\n",
    "            del g[j+1:]\n",
    "            if g[0][0] ==1:\n",
    "                min_size =min(min_size,i-g[0][1])\n",
    "        \n",
    "        return min_size +n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        if reduce(gcd, nums) != 1:\r\n",
    "            return -1\r\n",
    "        h = Counter(nums)\r\n",
    "        if h[1]:\r\n",
    "            return len(nums) - h[1]\r\n",
    "        for i in range(2, len(nums) + 1):\r\n",
    "            for j in range(0, len(nums) - i + 1):\r\n",
    "                if reduce(gcd, nums[j:j + i]) == 1:\r\n",
    "                    return len(nums) + i - 2\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ml=n=len(nums)\n",
    "        one=0\n",
    "        yes=False\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                one+=1\n",
    "            g=nums[i]\n",
    "            j=i\n",
    "            while g!=1 and j<n:\n",
    "                g=gcd(g,nums[j])\n",
    "                j+=1\n",
    "            if g==1:\n",
    "                ml=min(ml,j-i)\n",
    "                yes=True\n",
    "        if not yes :return -1\n",
    "        print(one,ml,n)\n",
    "        if ml==0:\n",
    "            return n-one\n",
    "        else:\n",
    "            return n+ml-2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        uniqNums = sorted(set(nums))\n",
    "        \n",
    "        N = len(nums)\n",
    "        ans = N\n",
    "        j = 0\n",
    "        for i in range(len(uniqNums)):\n",
    "            if i >= ans:\n",
    "                break\n",
    "            lower = uniqNums[i]\n",
    "            upper = lower + N - 1\n",
    "            while (j < len(uniqNums)) and uniqNums[j] <= upper:\n",
    "                j += 1\n",
    "            count = j - i\n",
    "            ans = min(ans, N - count)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "                \n",
    "        length = len(nums)\n",
    "        ret = length-1\n",
    "        nums.sort()\n",
    "        l_index = 0\n",
    "        r_index = 0\n",
    "\n",
    "        repeat_index = list() # the index repeat with the later element\n",
    "        repeat_presum = [0]*length # how many times repeat appear in the first i number\n",
    "        for i in range(length-1):\n",
    "            if nums[i]==nums[i+1]:\n",
    "                repeat_index.append(i)\n",
    "                repeat_presum[i+1]=repeat_presum[i]+1\n",
    "            else:\n",
    "                repeat_presum[i+1]=repeat_presum[i]\n",
    "\n",
    "\n",
    "        while l_index<length-1:\n",
    "            # move r_index to right position\n",
    "            l_num = nums[l_index]\n",
    "            max_num = l_num + length - 1\n",
    "            for i in range(r_index,length):\n",
    "                if nums[i]<=max_num:\n",
    "                    r_index=i\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            operations = l_index + (repeat_presum[r_index]-repeat_presum[l_index]) + (length-r_index-1)\n",
    "            ret = min(ret, operations)\n",
    "\n",
    "            # find same number\n",
    "            while l_index+1 < length and nums[l_index]==nums[l_index+1]:\n",
    "                l_index+=1\n",
    "            l_index+=1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        l, i = 0, 0\n",
    "        res = inf\n",
    "        dup = 0\n",
    "        while i < n:\n",
    "            right = nums[l] + n - 1\n",
    "            while i < n and nums[i] <= right:\n",
    "                if i >= 1 and nums[i] == nums[i-1]:\n",
    "                    dup += 1\n",
    "                i += 1\n",
    "            res = min(res, n - (i - l) + dup)\n",
    "            l += 1\n",
    "            if l < n and nums[l] == nums[l-1]:\n",
    "                dup -= 1\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        pres = [0, 1]\n",
    "        for i, num in enumerate(nums[1:], start=1):\n",
    "            if num == nums[i - 1]:\n",
    "                pres.append(pres[-1])\n",
    "            else:\n",
    "                pres.append(pres[-1] + 1)\n",
    "                \n",
    "        ans = n - 1\n",
    "        for i, num in enumerate(nums):\n",
    "            j = bisect.bisect_right(nums, num + n - 1)\n",
    "            ans = min(ans, n - (pres[j] - pres[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = (1 << 31)-1\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        repeat = 0\n",
    "        while right < n:\n",
    "            if right > 0 and nums[right-1] == nums[right]:\n",
    "                repeat += 1\n",
    "            while nums[left]+n-1 < nums[right]:\n",
    "                left += 1\n",
    "                if nums[left] == nums[left-1]:\n",
    "                    repeat -= 1\n",
    "            res = min(res, n-(right-left+1-repeat))\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        tmp = [nums[0]]\n",
    "        for i in range(1, n) :\n",
    "            if nums[i-1] != nums[i] :\n",
    "                tmp.append(nums[i])\n",
    "        n_t = len(tmp)\n",
    "        ans = inf\n",
    "        for i in range(n_t) :\n",
    "            ind = bisect_right(tmp,  tmp[i]+n-1)\n",
    "            ans = min(ans, n - ind + i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n,ans,x,same=len(nums),len(nums),0,0\n",
    "        for i in range(0,n):\n",
    "            if(i+1<n and nums[i]==nums[i+1]):same-=1;continue\n",
    "            while(x<n and nums[x]-nums[i]<n):\n",
    "                x+=1\n",
    "                if(x<n and nums[x]==nums[x-1]):same+=1\n",
    "            ans=min(ans,n-(x-i-same))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      nums.sort()\n",
    "      left = right = maxl = 0\n",
    "      repeat = [0] * n\n",
    "      k = 0\n",
    "      for i in range(1, n):\n",
    "        if nums[i] == nums[i-1]:\n",
    "          k += 1\n",
    "        repeat[i] = k\n",
    "      def findrepeat(i, j):\n",
    "        if i == 0:\n",
    "          return repeat[j]\n",
    "        if nums[i] == nums[i-1]:\n",
    "          return repeat[j] - repeat[i - 1] - 1\n",
    "        else:\n",
    "          return repeat[j] - repeat[i - 1]\n",
    "      while right < n:\n",
    "        if nums[right] - nums[left] < n:\n",
    "          maxl = max(maxl, right - left + 1 - findrepeat(left, right))\n",
    "          right += 1\n",
    "        else:\n",
    "          left += 1\n",
    "      return (n - maxl)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        ans = 1\n",
    "        overload = 0\n",
    "        for i in range(n):\n",
    "            if i != 0 and nums[i-1] == nums[i]:\n",
    "                overload += 1\n",
    "            while nums[i] - nums[j] > n - 1:\n",
    "                j += 1\n",
    "                if nums[j] == nums[j-1]:\n",
    "                    overload -= 1 \n",
    "            ans = max(ans, i - j + 1 - overload)\n",
    "        return n - ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = (1 << 31)-1\n",
    "        n = len(nums)\n",
    "        dq = deque()\n",
    "        for num in nums:\n",
    "            while len(dq) and dq[0]+n-1 < num:\n",
    "                dq.popleft()\n",
    "            if not len(dq) or dq[-1]!=num:\n",
    "                dq.append(num)\n",
    "            res = min(res, n-len(dq))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        j = 0\n",
    "        total = 0\n",
    "        for i in range(len(nums)):\n",
    "            while j < len(nums) and nums[j] - nums[i] <= len(nums) - 1:\n",
    "                if j == 0 or nums[j] > nums[j - 1]:\n",
    "                    total += 1\n",
    "                j += 1\n",
    "            ans = min(ans, len(nums) - total)\n",
    "            if i == 0 or nums[i] > nums[i - 1]:\n",
    "                total -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        l = 0 # 左端点\n",
    "        r = 0 # 右端点\n",
    "        t = 0 # 表示滑动窗口内不需要改动的数的个数\n",
    "        while l < n:\n",
    "            while r < n and nums[r] - nums[l] <= n - 1:\n",
    "                # 不能有重复\n",
    "                if r > l and nums[r] != nums[r-1]:\n",
    "                    t += 1\n",
    "                elif r == l:\n",
    "                    t += 1\n",
    "                r += 1\n",
    "            l += 1\n",
    "            # n - t 表示需要改动的数的个数\n",
    "            ans = min(n-t, ans)\n",
    "            # 当nums[l] == nums[l-1] 时, 以nums[l-1]为左端点中 nums[l] 被当作重复值了\n",
    "            if l < n and nums[l] != nums[l-1]:\n",
    "                t -= 1\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nn = [a for a, b in pairwise(nums) if a != b] + [nums[-1]]\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        for i, num in enumerate(nn):\n",
    "            idx = bisect.bisect(nn, num + n - 1)\n",
    "            ans = min(ans, n - (idx - i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        l = 0\n",
    "        r = 0\n",
    "        t = 0\n",
    "        while l < n:\n",
    "            while r < n and nums[r] - nums[l] <= n - 1:\n",
    "                if r > l and nums[r] != nums[r-1]:\n",
    "                    t += 1\n",
    "                if r == l:\n",
    "                    t += 1\n",
    "                r += 1\n",
    "            l += 1\n",
    "            ans = min(n-t, ans)\n",
    "            if l < n and nums[l] != nums[l-1]:\n",
    "                t -= 1\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.minOperations([44,28,33,49,4,2,35,28,25,38,47,20,14,30,27,38,42,14,34])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        l = 0 # 左端点\n",
    "        r = 0 # 右端点\n",
    "        t = 0 # 表示不需要改动的数的个数\n",
    "        while l < n:\n",
    "            while r < n and nums[r] - nums[l] <= n - 1:\n",
    "                # 不能有重复\n",
    "                if r > l and nums[r] != nums[r-1]:\n",
    "                    t += 1\n",
    "                elif r == l:\n",
    "                    t += 1\n",
    "                r += 1\n",
    "            l += 1\n",
    "            ans = min(n-t, ans)\n",
    "            # nums[l] == nums[l-1] 时 nums[l] 未被计算为“可用”\n",
    "            if l < n and nums[l] != nums[l-1]:\n",
    "                t -= 1\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.minOperations([44,28,33,49,4,2,35,28,25,38,47,20,14,30,27,38,42,14,34])\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        nums = sorted(nums)\n",
    "\n",
    "        left,right = 0,0\n",
    "        cnt = 0\n",
    "        visited = set()\n",
    "        max_val = 0\n",
    "        for right in range(n):\n",
    "            if nums[right]<=nums[left]+n-1:\n",
    "              \n",
    "                visited.add(nums[right])\n",
    "                \n",
    "            else:\n",
    "                while nums[right]-nums[left]>=n:\n",
    "                    if nums[left] in visited:\n",
    "                        visited.remove(nums[left])\n",
    "                    left += 1\n",
    "                \n",
    "               \n",
    "        \n",
    "                visited.add(nums[right])\n",
    "           \n",
    "\n",
    "            max_val = max(len(visited),max_val)\n",
    "        return n-max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = n - 1\n",
    "        nums.sort()\n",
    "        snums = set(nums)\n",
    "        nums_no_dup = list(snums)\n",
    "        nums_no_dup.sort()\n",
    "        # print(nums, nums_no_dup)\n",
    "        for i, num in enumerate(nums_no_dup):\n",
    "            expect = i + n - 1\n",
    "            idx = self.findidx(nums_no_dup, len(nums_no_dup), num + n - 1)\n",
    "            res = min(res, (n - (idx - i)))\n",
    "            # print(i, num, n, idx, (n - (idx - i)), res)\n",
    "\n",
    "            newidx = bisect_right(nums_no_dup, num+n-1)\n",
    "            # print(idx, newidx)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def findidx(self, nums, n, target):\n",
    "        # print( nums, n, target)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid + 1\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                if mid < n-1 and nums[mid+1] > target:\n",
    "                    return mid + 1\n",
    "                left = mid + 1\n",
    "\n",
    "        return n\n",
    "                \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))  \n",
    "        ans = n\n",
    "        for i, start in enumerate(nums):\n",
    "            end = start + n - 1  \n",
    "            idx = bisect_right(nums, end)  # Find right insert position\n",
    "            uniqueLen = idx - i\n",
    "            ans = min(ans, n - uniqueLen)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # neetcode\n",
    "        length = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        res = length\n",
    "        r = 0\n",
    "        for l in range(len(nums)):\n",
    "            # range: nums[l], nums[l] + length - 1\n",
    "            while r < len(nums) and nums[r] < nums[l] + length:\n",
    "                r += 1\n",
    "            window = r - l \n",
    "            res = min(res, length - window)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        m = len(nums)  # 排重之后的数量\n",
    "        nums.sort()\n",
    "        ans = n\n",
    "        r = 0\n",
    "        for l in range(m):\n",
    "            mx = nums[l] + n - 1\n",
    "            r = max(r, l)\n",
    "            while r < m and nums[r] <= mx:\n",
    "                r += 1\n",
    "            ans = min(ans, l + n - r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            if nums[j] >= nums[i] + N:\n",
    "                cur = j - i\n",
    "                if cur > ret:\n",
    "                    ret = cur\n",
    "                while nums[j] >= nums[i] + N:\n",
    "                    i += 1\n",
    "        cur = n - i\n",
    "        if cur > ret:\n",
    "            ret = cur\n",
    "        return N - ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        m, left = len(nums), 0\n",
    "        for right in range(m):\n",
    "            if nums[right] - nums[left] >= n:\n",
    "                left += 1\n",
    "\n",
    "        return n - (m - left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        an = len(a)\n",
    "\n",
    "        cur = 0\n",
    "        r = 0\n",
    "        for l in range(an):\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\n",
    "                r += 1\n",
    "            cur = max(cur, r - l + 1)\n",
    "\n",
    "        return n - cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        new_nums = sorted(set(nums))\n",
    "        \n",
    "        for i in range(len(new_nums)):\n",
    "            left = new_nums[i]\n",
    "            right = left + n - 1\n",
    "            j = bisect_right(new_nums, right)\n",
    "            count = j - i\n",
    "            ans = min(ans, n - count)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        ans = n\n",
    "        l = 0\n",
    "        for r, v in enumerate(nums):\n",
    "            while nums[l] < v - n + 1:\n",
    "                l += 1\n",
    "            \n",
    "            ans = min(ans, n - (r - l + 1))\n",
    "            \n",
    "        r = 0\n",
    "        for l, v in enumerate(nums):\n",
    "            while r + 1 < len(nums) and nums[r+1] <= v + n - 1:\n",
    "                r += 1\n",
    "            \n",
    "            ans = min(ans, n - (r - l + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        unique_nums = sorted(list(set(nums)))\n",
    "        ans = n - 1\n",
    "        m = len(unique_nums)\n",
    "        for i in range(m):\n",
    "            start_val, end_val = unique_nums[i], unique_nums[i] + n - 1\n",
    "            idx = bisect_right(unique_nums, end_val)\n",
    "            overlap = idx - i\n",
    "            if n - overlap < ans:\n",
    "                ans = n - overlap\n",
    "        return ans\n",
    "        # m = len(unique_nums)\n",
    "        # max_length = 1\n",
    "        # idx = 0\n",
    "        # while idx < m:\n",
    "        #     i = idx\n",
    "        #     while i + 1 < m and unique_nums[i+1] - unique_nums[i] == 1:\n",
    "        #         i += 1\n",
    "        #     if i - idx + 1 > max_length:\n",
    "        #         max_length = i - idx + 1\n",
    "        #     idx = i + 1\n",
    "        \n",
    "        # return n - max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        numsSize = len(nums)\n",
    "\n",
    "        numsUiqueSort = sorted(set(nums))\n",
    "        numsUiqueSortSize = len(numsUiqueSort)\n",
    "\n",
    "        retVal = numsSize\n",
    "        j = 0\n",
    "        for i in range(numsUiqueSortSize):\n",
    "            while (j < numsUiqueSortSize) and (numsUiqueSort[j] < numsUiqueSort[i] + numsSize):\n",
    "                j += 1\n",
    "            count = j - i\n",
    "            retVal = min(retVal, numsSize - count)\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = set(nums)\n",
    "        nums = list(s)\n",
    "\n",
    "        nums.sort()\n",
    "        l, i = 0, 0\n",
    "        res = inf\n",
    "        while l < len(nums):\n",
    "            right = nums[l] + n - 1\n",
    "            while i < len(nums) and nums[i] <= right:\n",
    "                res = min(res, n - (i - l + 1))\n",
    "                i += 1\n",
    "            l += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = sorted(set(nums))\n",
    "        m, left = len(a), 0\n",
    "        for i in range(m):\n",
    "            if a[i] - a[left] >= n: left += 1\n",
    "        return n - (m - left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 第一点 重复元素必改 改成什么样子后面决定\n",
    "        target = len(nums)-1\n",
    "        t = len(nums)-len(set(nums))\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        # 滑动窗口 找到最大的窗口\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] - nums[left] > target:\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return t+len(nums)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = sorted(set(nums))\n",
    "        m, left = len(a), 0\n",
    "        for i in range(m):\n",
    "            if a[i] - a[left] >= n: left += 1\n",
    "        return n - (m - left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "\r\n",
    "        a = list(set(nums))\r\n",
    "        a.sort()\r\n",
    "        an = len(a)\r\n",
    "\r\n",
    "        cur = 0\r\n",
    "        r = 0\r\n",
    "        for l in range(an):\r\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\r\n",
    "                r += 1\r\n",
    "            cur = max(cur, r - l + 1)\r\n",
    "\r\n",
    "        return n - cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        nums = sorted(set(nums))\n",
    "       \n",
    "        # res = 1\n",
    "        # cur = 1\n",
    "        # l = 0\n",
    "        # n = len(nums)\n",
    "        # start = nums[l]\n",
    "        # for r in range(1, len(nums)):\n",
    "        #     if nums[r] <= start + n - 1:\n",
    "        #         cur += 1\n",
    "        #         res = max(res,cur)\n",
    "        #     else:\n",
    "        #         while l < r and nums[l] < nums[r] - n :\n",
    "        #             l += 1\n",
    "        #         cur = 1\n",
    "        #         start = nums[l]\n",
    "  \n",
    "        # return n - res\n",
    "\n",
    "        \n",
    "\n",
    "        res = 1\n",
    "      \n",
    "        l = 0\n",
    "        \n",
    "\n",
    "\n",
    "        for r in range(1, len(nums)):\n",
    "            if nums[r] <= nums[l] + n - 1:\n",
    "                \n",
    "                res = max(res,r - l + 1)\n",
    "            else:\n",
    "                while l < r and nums[l] < nums[r] - n +1:\n",
    "                    l += 1\n",
    "              \n",
    "        return n - res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # nums.sort()\n",
    "\n",
    "        \n",
    "\n",
    "        # res = 1\n",
    "      \n",
    "        # l = 0\n",
    "        # n = len(nums)\n",
    "        # start = nums[l]\n",
    "        # dic = set()\n",
    "        # dic.add(start)\n",
    "        # print(dic)\n",
    "        # for r in range(1, len(nums)):\n",
    "        #     if nums[r] <= start + n - 1:\n",
    "        #         dic.add(nums[r])\n",
    "        #         res = max(res,len(dic))\n",
    "        #         print(dic)\n",
    "        #     else:\n",
    "        #         while l < r and nums[l] < nums[r] - n + 1:\n",
    "        #             dic.remove(nums[l])\n",
    "        #             l += 1\n",
    "        #         start = nums[l]\n",
    "        #         dic.add(nums[l])\n",
    "                \n",
    "        # return n - res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        arr = sorted(set(nums))\n",
    "        ans = inf\n",
    "        for i, x in enumerate(arr):\n",
    "            j = bisect_right(arr, x + n - 1)\n",
    "            ans = min(ans, n - j + i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        l = len(nums)#数组长度\n",
    "        nums = sorted(set(nums))#去重排序\n",
    "        c = l - len(nums)#排序数组,用于寻找边界内的数字数量\n",
    "        s = [nums.pop(0)]\n",
    "        res = l - 1\n",
    "        for i, n in enumerate(nums):#遍历数组\n",
    "            idx = bisect.bisect_left(s, n - l + 1)#二分寻找左边界下标\n",
    "            res = min(res, l - (i - idx + 2))#数组长度 - 已包含数字数量\n",
    "            s.append(n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        res = float('inf')\n",
    "        for l, num in enumerate(nums):  # 以每一位num作为最小值\n",
    "            r = bisect.bisect_right(nums, num + n - 1)  # 找到最大值\n",
    "            res = min(res, n - (r - l))  # 总长度-区间长度=需要弥补的个数\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        new_nums = sorted(set(nums))\n",
    "        j = 0\n",
    "\n",
    "        for i in range(len(new_nums)):\n",
    "            while j < len(new_nums) and new_nums[j] < new_nums[i] + n:\n",
    "                j += 1\n",
    "\n",
    "            count = j - i\n",
    "            ans = min(ans, n - count)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        new_nums = sorted(set(nums))\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(len(new_nums)):\n",
    "            left = new_nums[i]\n",
    "            right = left + n - 1\n",
    "            j = bisect_right(new_nums, right)\n",
    "           \n",
    "            count = j - i\n",
    "            ans = min(ans, n - count)\n",
    "\n",
    "        \n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(list(set(nums)))\n",
    "        res = inf\n",
    "        for i, e in enumerate(nums):\n",
    "            where = bisect_right(nums, e+n-1)\n",
    "            res = min(res, i + n - where)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        d = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > d-1:\n",
    "                m = max(m, j-i)\n",
    "                i += 1\n",
    "\n",
    "        if nums[n-1] - nums[i] < d:\n",
    "                m = max(m, n-i)\n",
    "        return d-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        a = sorted(set(nums))\r\n",
    "        m, left = len(a), 0\r\n",
    "        for i in range(m):\r\n",
    "            if a[i] - a[left] >= n: left += 1\r\n",
    "        return n - (m - left)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(list(set(nums)))\n",
    "        left = 0\n",
    "        minop = n\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] - nums[left] + 1 > n:\n",
    "                left += 1\n",
    "            minop = min(n - (right - left + 1), minop)\n",
    "        return minop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 获得nums的长度\n",
    "        n = len(nums)\n",
    "\n",
    "        # 将nums转换为集合以去除重复项，然后对其进行排序\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        an = len(a)\n",
    "\n",
    "        # 初始化当前连续数字的数量和滑动窗口的右边界\n",
    "        cur = 0\n",
    "        r = 0\n",
    "        \n",
    "        # 使用滑动窗口方法来找到nums中的最大连续子数组\n",
    "        for l in range(an):\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\n",
    "                r += 1\n",
    "            cur = max(cur, r - l + 1)\n",
    "\n",
    "        # 返回需要操作的元素的数量\n",
    "        return n - cur\n",
    "\n",
    "# 测试\n",
    "solution = Solution()\n",
    "print(solution.minOperations([4, 2, 5, 3])) # 输出：0\n",
    "print(solution.minOperations([1, 2, 3, 5, 6])) # 输出：1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        delete = 0\n",
    "        i = 1\n",
    "        mx = 1\n",
    "        MAXN = 1e10\n",
    "        ans = MAXN+10\n",
    "        l,r = 0,1\n",
    "        n = len(nums)\n",
    "        tmp = list(set(nums))\n",
    "        tmp.sort()\n",
    "        \n",
    "        while r < len(tmp):\n",
    "            if l < r and tmp[l] < tmp[r]-n+1:\n",
    "                l += 1\n",
    "            r += 1\n",
    "        return n-(r-l)\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 第一点 重复元素必改 改成什么样子后面决定\n",
    "        target = len(nums)-1\n",
    "        t = len(nums)-len(set(nums))\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        # 滑动窗口 找到最大的窗口\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] - nums[left] > target:\n",
    "                left += 1\n",
    "            res = max(res,right-left+1)\n",
    "        return t+len(nums)-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        c = l - len(nums)\n",
    "        s = [nums.pop(0)]\n",
    "        res = l - 1\n",
    "        for i, n in enumerate(nums):\n",
    "            idx = bisect.bisect_left(s, n - l + 1) #二分寻找左边界下标\n",
    "            res = min(res, l - (i - idx + 2)) #数组长度 - 已包含数字数量\n",
    "            s.append(n)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 获得nums的长度\n",
    "        n = len(nums)\n",
    "\n",
    "        # 将nums转换为集合以去除重复项，然后对其进行排序\n",
    "        a = list(set(nums))\n",
    "        a.sort()\n",
    "        an = len(a)\n",
    "\n",
    "        # 初始化当前连续数字的数量和滑动窗口的右边界\n",
    "        cur = 0\n",
    "        r = 0\n",
    "        \n",
    "        # 使用滑动窗口方法来找到nums中的最大连续子数组\n",
    "        for l in range(an):\n",
    "            while r + 1 < an and a[r + 1] - a[l] <= n - 1:\n",
    "                r += 1\n",
    "            cur = max(cur, r - l + 1)\n",
    "\n",
    "        # 返回需要操作的元素的数量\n",
    "        return n - cur\n",
    "\n",
    "# 测试\n",
    "solution = Solution()\n",
    "print(solution.minOperations([4, 2, 5, 3])) # 输出：0\n",
    "print(solution.minOperations([1, 2, 3, 5, 6])) # 输出：1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = sorted(set(nums))\n",
    "        mx = i = 0\n",
    "        for j, x in enumerate(a):\n",
    "            while a[i] <= x - n: i += 1\n",
    "            mx = max(mx, j - i + 1)\n",
    "        return n - mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        m = len(nums)\n",
    "        ans = inf\n",
    "        for i in range(m):\n",
    "            l, r = 0, i\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if nums[mid] >= nums[i] - n + 1:\n",
    "                    r = mid\n",
    "                else: l = mid + 1\n",
    "            ans = min(ans, n - (i - l + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        s = [nums.pop(0)]\n",
    "        res = n - 1\n",
    "        for i, num in enumerate(nums):\n",
    "            idx = bisect_left(s, num - n + 1)\n",
    "            res = min(res, n - (i - idx + 2))\n",
    "            s.append(num)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        temp=list(set(nums))\n",
    "        target=len(nums)-1\n",
    "        t=len(nums)-len(temp)\n",
    "        temp.sort()\n",
    "        n=len(temp)-1\n",
    "        ans=0\n",
    "        l=0\n",
    "        for r in range(n+1):\n",
    "            while temp[r]-temp[l]>=target+1:\n",
    "                l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        return t+n+1-ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        arr = []\n",
    "        res = float('inf')\n",
    "        for i, num in enumerate(nums):  # 以每一位num作为最大值\n",
    "            l = bisect.bisect_left(arr, num - n + 1)  # 二分查找最小值\n",
    "            res = min(res, n - (i - l + 1))\n",
    "            arr.append(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        max_diff=n-1\n",
    "        nums=list(set(nums))\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        m=len(nums)\n",
    "        left=0\n",
    "        res=inf\n",
    "        if n==1:\n",
    "            return 0\n",
    "        for right in range(1,m):\n",
    "            while nums[right]>nums[left]+max_diff and right>left:\n",
    "                left+=1\n",
    "            res=min(res,n-(right-left+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        L = len(nums)\n",
    "        nums = sorted(set(nums))\n",
    "        r = 0\n",
    "        res = L\n",
    "        for i,n in enumerate(nums):\n",
    "            while r<len(nums) and nums[r]<n+L:\n",
    "                r += 1\n",
    "            res = min(res, L-(r-i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(list(set(nums)))\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        m = len(nums)\n",
    "        for i in range(m):\n",
    "            if n - i < ans:\n",
    "                return  n - ans\n",
    "            num = nums[i] + n - 1\n",
    "            r = bisect.bisect(nums,num)\n",
    "            if r < m and nums[r] != num or r == m:\n",
    "                ans = max(ans, r - i)\n",
    "            else:\n",
    "                ans = max(ans, r - i + 1)\n",
    "        return n - ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        seen = set()\n",
    "        for i, v in enumerate(nums):\n",
    "            if v not in seen:\n",
    "                seen.add(v)\n",
    "            else:\n",
    "                nums[i] = inf\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        j = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            while j < n and nums[j] < v + n:\n",
    "                j += 1\n",
    "            if (s := n - (j - i)) < ans:\n",
    "                ans = s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "\n",
    "        if nums[n-1] - nums[i] < n:\n",
    "                m = max(m, len(d))\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "\n",
    "        if nums[n-1] - nums[i] < n:\n",
    "                m = max(m, len(d))\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            if j == n-1 and nums[j] - nums[i] < n:\n",
    "                m = max(m, len(set(nums[i:])))\n",
    "\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        m = 0\n",
    "        i = 0\n",
    "        d = {}\n",
    "        for j in range(n):\n",
    "            while nums[j] - nums[i] > n-1:\n",
    "                m = max(m, len(d))\n",
    "                d[nums[i]] -= 1\n",
    "                if d[nums[i]] == 0:\n",
    "                    del d[nums[i]]\n",
    "                i += 1\n",
    "            d[nums[j]] = d.get(nums[j], 0) + 1\n",
    "            if j == n-1 and nums[j] - nums[i] < n:\n",
    "                m = max(m, len(d))\n",
    "\n",
    "        return n-m"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
